package datastructure.deque;

import java.util.Iterator;

/**
 * 基于循环数组实现
 *
 * @author 杨 强
 * @package datastructure.deque
 * @createTime 2023-03-15 22:38
 */
public class ArrayDeque<E> implements Deque<E>, Iterable<E> {

    public static void main(String[] args) {
        ArrayDeque<Integer> deque = new ArrayDeque(5);
        deque.offerFirst(1);
        deque.offerFirst(2);
        deque.offerLast(3);
        deque.offerLast(4);
        // 1 2 3 4
        Iterator<Integer> iterator = deque.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

    @Override
    public boolean offerFirst(E e) {
        // 判断满
        if (isFull()){
            return false;
        }
        // 头指针减一
        head = dec(head, array.length);
        // 数据插入到头指针移动后的位置
        array[head] = e;
        return true;

    }

    @Override
    public boolean offerLast(E e) {
        // 判断满
        if (isFull()) {
            return false;
        }
        // 数据直接插入到尾指针的位置
        array[tail] = e;
        // 尾指针下标加一
        tail = inc(tail, array.length);
        return true;
    }

    @Override
    public E pollFirst() {
        // 判断空
        if (isEmpty()){
            return null;
        }
        // 根据头不插入知道,头部指针的位置就是头元素
        E e = array[head];
        // 把元素置为空,是为了引用类型的时候释放对象的堆内存.
        array[head] = null;
        // 指针向前移动一位
        head = inc(head, array.length);
        // 返回值
        return e;
    }

    @Override
    public E pollLast() {
        // 判断空
        if (isEmpty()) {
            return null;
        }
        // 根据尾插入元素的方法我知道,尾部指针的前一个指针的位置才是尾元素
        tail = dec(tail, array.length);
        // 得到值
        E e = array[tail];
        // 把元素置为空,是为了引用类型的时候释放对象的堆内存.
        array[tail] = null;
        return e;
    }

    @Override
    public E peekFirst() {
        if (isEmpty()) {
            return null;
        }
        return array[head];
    }

    @Override
    public E peekLast() {
        if (isEmpty()) {
            return null;
        }
        return array[dec(tail, array.length)];
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    @Override
    public boolean isFull() {
        // 判断满需要分两种情况,一种是head大于tail, 一种是tail大于head
        // 这里需要看思路中的分析,画图可以很直观的看出来
        if (head > tail){
            return head - tail == 1;
        }else if (tail > head){
            return tail - head == array.length - 1;
        }else {
            return false;
        }
    }

    /**
     * 底层储存数据的数组
     */
    private E[] array;
    /**
     * 头指针
     */
    private int head;
    /**
     * 尾指针
     */
    private int tail;
    /**
     * 构造器
     * @param capacity 容量
     */
    public ArrayDeque(int capacity) {
        // 为了给一个位置给尾指针所以初始数组要指定容量加一
        array = (E[]) new Object[capacity + 1];
    }

    /**
     * 指针加一的方法
     * @param i 当前指针的位置
     * @param length 数组的长度
     * @return
     */
    private static int inc(int i, int length) {
        if (i + 1 >= length) {
            return 0;
        }
        return i + 1;
    }

    /**
     * 指针减一的方法
     * @param i 当前指针的位置
     * @param length 数组的长度
     * @return
     */
    private static int dec(int i, int length) {
        if (i - 1 < 0) {
            return length - 1;
        }
        return i - 1;
    }


    /**
     * 迭代器
     * @return
     */
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;
            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public E next() {
                E e = array[p];
                p = inc(p, array.length);
                return e;
            }
        };
    }
}
